// 先序遍历
var preorderTraversal = function (root) {
    let result = [];
    if (root == null) return result;
    getPreorderTraversal(root, result);
    return result;
};

// 递归遍历
// function getPreorderTraversal(root, result) {
//     if (root == null) return;
//     result.push(root.val);
//     getPreorderTraversal(root.left, result);
//     getPreorderTraversal(root.right, result);
// }
function getPreorderTraversal(root, result) {
    if (root == null) return;
    let queue = [];
    queue.push(root);
    while (queue.length > 0) {
        let currentNode = queue.pop();
        result.push(currentNode.val);
        if (currentNode.right) {
            queue.push(currentNode.right);
        }
        if (currentNode.left) {
            queue.push(currentNode.left);
        }
    }
}
// 中序遍历
var inorderTraversal = function (root) {
    let result = [];
    if (root == null) return result;
    getInorderTraversal(root, result);
    return result;
};

// 递归遍历
// function getInorderTraversal(root, result) {
//     if (root == null) return;
//     getInorderTraversal(root.left, result);
//     result.push(root.val);
//     getInorderTraversal(root.right, result);
// }

function getInorderTraversal(root, result) {
    if (root == null) return;
    let queue = [];
    while (root != null || queue.length > 0) {
        while (root) {
            queue.push(root);
            root = root.left;
        }
        root = queue.pop();
        root.push(currentNode.val);
        root = root.right;
    }
}
// 后序遍历
var postorderTraversal = function (root) {
    let result = [];
    if (root == null) return result;
    getPostorderTraversal(root, result);
    return result;
};
// 递归遍历
// function getPostorderTraversal(root, result) {
//     if (root == null) return;
//     getPostorderTraversal(root.left, result);
//     getPostorderTraversal(root.right, result);
//     result.push(root.val);
// }

function getPostorderTraversal(root, result) {
    if (root == null) return;
    let queue = [];
    while (root != null || queue.length > 0) {
        while (root) {
            queue.push(root);
            result.unshift(root.val);
            root = root.right;
        }
        root = queue.pop();
        root = root.left;
    }
}

// 102. 二叉树的层序遍历
// 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

var levelOrder = function (root) {
    let res = [];
    if (root == null) return res;
    let queue = [];
    queue.push(root);
    while (queue.length > 0) {
        let levelVal = [];
        let levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            levelVal.push(node.val);
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        res.push(levelVal);
    }
    return res;
};

// 107. 二叉树的层序遍历 II
// 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)
var levelOrderBottom = function (root) {
  let res = [];
  if (root === null) return res;
  let queue = [];
  queue.push(root);
  while (queue.length > 0) {
    let level = [];
    let qLen = queue.length;
    for (let i = 0; i < qLen; i++){
      let cur = queue.shift();
      level.push(cur.val);
      if (cur.left) queue.push(cur.left);
      if(cur.right) queue.push(cur.right)
    }
    res.unshift(level);
  }
  return res;
};

// 103. 二叉树的锯齿形层序遍历
// 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
var zigzagLevelOrder = function(root) {
    let res = [];
    if(root === null) return res;
    let queue = [];
    queue.push(root);
    let flag = true;
    while(queue.length>0){
        let levelLength = queue.length;
        let levelVal = [];
        for(let i = 0; i<levelLength; i++) {
            const node = queue.shift();
            if(flag){
                levelVal.push(node.val);
            } else {
                levelVal.unshift(node.val);
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        flag = !flag;
        res.push(levelVal);
    }
    return res;
};

// 199. 二叉树的右视图：给定一个二叉树的 根节点 root，想象自己站在它的右侧，
//      按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

var rightSideView = function (root) {
    let res = [];
    let queue = [];
    queue.push(root);
    while (queue.length > 0 && root != null) {
        let length = queue.length;
        while (length--) {
            let node = queue.shift();
            if (length == 0) {
                res.push(node.val);
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return res;
};

// 543. 二叉树的直径
var diameterOfBinaryTree = function(root) {
    let res = 1
    let backtracking = (node) => {
        if(node===null) return 0
        let left = backtracking(node.left)
        let right = backtracking(node.right)
        res = Math.max(res, left + right + 1)
        return Math.max(left, right) + 1
    }
    backtracking(root)
    return res - 1
};

// 662. 二叉树最大宽度
var widthOfBinaryTree = function (root) {
    let res = 0;
    if (root == null) return res;
    let queue = [];
    queue.push(root);
    root.val = 1;
    while (queue.length > 0) {
        let levelSize = queue.length;
        let left = queue[0].val;
        let right = queue[queue.length - 1].val;
        res = Math.max(res, right - left + 1);
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            let currVal = node.val;
            if (node.left) {
                node.left.val = currVal * 2;
                queue.push(node.left);
            }
            if (node.right) {
                node.right.val = currVal * 2 + 1;
                queue.push(node.right);
            }
        }
    }
    return res;
};


// 98. 验证二叉搜索树
var isValidBST = function(root) {
    if(root===null) return true;
    return isValidBST1(root, null, null);
};

function isValidBST1(root, min, max){
    if(root=== null) return true;
    if(min != null && root.val <= min.val) return false;
    if(max != null && root.val >= max.val) return false;

    return isValidBST1(root.left, min, root)
        && isValidBST1(root.right, root, max)
}
// 108. 将有序数组转换为二叉搜索树
var sortedArrayToBST = function(nums) {
    const length = nums.length;
    if(length === 0) return null;
    return sortedArrayToBST1(nums, 0, length-1);
};

function sortedArrayToBST1(nums, i, j){
    if(i>j) return null;
    const mid = i + Math.floor((j - i)/2);
    const root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST1(nums, i, mid-1);
    root.right = sortedArrayToBST1(nums, mid+1, j);
    return root;
}

// 109. 有序链表转换二叉搜索树
var sortedListToBST = function(head) {
    if(head===null) return null;
    let nodeList = [];
    while(head != null){
        nodeList.push(head.val);
        head = head.next;
    }
    return sortedListToBST1(nodeList, 0, nodeList.length-1)
};

function sortedListToBST1(nodeList, i, j){
    if(i>j) return null;
    const mid = i + Math.floor((j-i)/2);
    const root = new TreeNode(nodeList[mid]);
    root.left = sortedListToBST1(nodeList, i, mid-1);
    root.right = sortedListToBST1(nodeList, mid+1, j);
    return root;
}

// 100. 相同的树
var isSameTree = function (p, q) {
    if (p == null && q == null) {
        return true;
    } else if (q == null || p == null) {
        return false;
    } else if (p.val != q.val) {
        return false;
    } else {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
};

// 101 对称二叉树
var isSymmetric = function (root) {
    return check(root, root);
};

function check(nodeA, nodeB) {
    if (nodeA == null && nodeB == null) return true;
    if (nodeA == null || nodeB == null) return false;
    return nodeA.val == nodeB.val
        && check(nodeA.left, nodeB.right)
        && check(nodeA.right, nodeB.left);
}

// 104 二叉树的最大深度
var maxDepth = function (root) {
    if (root == null) return 0;
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

// 112 路径总和：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，
// 判断该树中是否存在 根节点到叶子节点 的路径，
// 这条路径上所有节点值相加等于目标和 targetSum 。
var hasPathSum = function(root, targetSum) {
    if(root===null) return false;
    if(root.left === null && root.right === null && root.val === targetSum) return true;
    return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
};

// 113 路径总和 II：给你二叉树的根节点 root 和一个整数目标和 targetSum ，
// 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

var hasPathSum = function (root, targetSum) {
    let res = [];
    let path = [];
    dfs(root, targetSum, 0, path, res);
    return res;
};

function dfs(root, targetSum, tatol, path, res) {
    if (root == null) return;
    path.push(root.val);
    tatol += root.val;
    if (root.left == null && root.right == null) {
        if (targetSum == tatol) {
            res.push([...path]);
        }
    } else {
        root.left && dfs(root.left, targetSum, tatol, path, res);
        root.right && dfs(root.right, targetSum, tatol, path, res);
    }
    path.pop();
}


// 129. 求根节点到叶节点数字之和
var sumNumber = function (root) {
    return dfs(root, 0);
}

function dfs(root, sum, tatol, path, res) {
    if (root == null) return 0;
    sum = sum * 10 + root.val;
    if (root.left == null && root.right == null) return sum;
    return dfs(root.left, sum) + dfs(root.right, sum);
}

// 235、236 最近公共祖先
// a、当前节点是空节点、当前节点是 q、当前节点是 p，返回当前节点；
// b、左右子树都找到:返回当前节点；
// 只有左子树找到:返回递归左子树的结果；
// 只有右子树找到:返回递归右子树的结果；
// 左右子树都没有找到:返回空节点；
var lowestCommonAncestor = function(root, p, q) {
    if(root === null || root.val === p.val || root.val === q.val){
        return root;
    }
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    if(left && right) return root;
    if(left) return left;
    if(right) return right;
    return null;
};


